import java.util.LinkedList;
import java.util.Queue;

public class Solution1210 {
    public int minimumMoves(int[][] grid) {
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{0,0,0});
        int[][][] visit=new int[grid.length][grid[0].length][2];
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                visit[i][j][0]=visit[i][j][1]=Integer.MAX_VALUE;
            }
        }
        visit[0][0][0]=0;
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            if (t[2]==0){
                if (t[1]+2<grid[0].length && grid[t[0]][t[1]+2]==0 && visit[t[0]][t[1]+1][0]==Integer.MAX_VALUE){
                    visit[t[0]][t[1]+1][0]=visit[t[0]][t[1]][0]+1;
                    queue.offer(new int[]{t[0],t[1]+1,0});
                }
                if (t[0]+1<grid.length && grid[t[0]+1][t[1]]==0 && grid[t[0]+1][t[1]+1]==0 && visit[t[0]][t[1]][1]==Integer.MAX_VALUE){
                    visit[t[0]][t[1]][1]=visit[t[0]][t[1]][0]+1;
                    queue.offer(new int[]{t[0],t[1],1});
                }
                if (t[0]+1<grid.length && grid[t[0]+1][t[1]]==0 && grid[t[0]+1][t[1]+1]==0 && visit[t[0]+1][t[1]][0]==Integer.MAX_VALUE){
                    visit[t[0]+1][t[1]][0]=visit[t[0]][t[1]][0]+1;
                    queue.offer(new int[]{t[0]+1,t[1],0});
                }
            }else{
                if (t[0]+2<grid.length && grid[t[0]+2][t[1]]==0 && visit[t[0]+1][t[1]][1]==Integer.MAX_VALUE){
                    visit[t[0]+1][t[1]][1]=visit[t[0]][t[1]][1]+1;
                    queue.offer(new int[]{t[0]+1,t[1],1});
                }
                if (t[1]+1<grid[0].length && grid[t[0]][t[1]+1]==0 && grid[t[0]+1][t[1]+1]==0 && visit[t[0]][t[1]][0]==Integer.MAX_VALUE){
                    visit[t[0]][t[1]][0]=visit[t[0]][t[1]][1]+1;
                    queue.offer(new int[]{t[0],t[1],0});
                }
                if (t[1]+1<grid[0].length && grid[t[0]][t[1]+1]==0 && grid[t[0]+1][t[1]+1]==0 && visit[t[0]][t[1]+1][1]==Integer.MAX_VALUE){
                    visit[t[0]][t[1]+1][1]=visit[t[0]][t[1]][1]+1;
                    queue.offer(new int[]{t[0],t[1]+1,1});
                }
            }
        }
        int ans=visit[grid.length-1][grid[0].length-2][0];
        return ans==Integer.MAX_VALUE?-1:ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1210().minimumMoves(new int[][]{{0,0,0,0,0,1},{1,1,0,0,1,0},{0,0,0,0,1,1},{0,0,1,0,1,0},{0,1,1,0,0,0},{0,1,1,0,0,0}}));
    }
}
